#!/usr/bin/env python3

"""
Given a 2D board and a word, find if the word exists in the grid.

The word can be constructed from letters of sequentially adjacent cell, where "adjacent" cells are those horizontally or vertically neighboring. The same letter cell may not be used more that once. 
"""

class Solution:
    def exist(self, board, word):
        word_start_ch = word[0]
        m = len(board)
        n = len(board[0])
        contain_chars = set()
        for m_index in range(m):
            for n_index in range(n):
                ch = board[m_index][n_index]
                if ch != word_start_ch:
                    continue
                if self.check_exist(board, word, m_index, n_index, 0, contain_chars):
                    return True
        return False

    def check_exist(self, board, word, start_m, start_n, word_start, contain_chars):
        contain_chars.add((start_m, start_n))
        if word_start == len(word) - 1:
            return True
        left_point = (start_m, start_n - 1)
        right_point = (start_m, start_n + 1)
        top_point = (start_m - 1, start_n)
        bottom_point = (start_m + 1, start_n)
        check_points = [left_point, right_point, top_point, bottom_point]
        for point in check_points:
            if point in contain_chars:
                continue
            if point[0] < 0 or point[0] >= len(board):
                continue
            if point[1] < 0 or point[1] >= len(board[0]):
                continue
            ch = board[point[0]][point[1]]
            if ch != word[word_start + 1]:
                continue
            if self.check_exist(board, word, point[0], point[1], word_start + 1, contain_chars):
                return True

        contain_chars.remove((start_m, start_n))
        return False
        
                
                


if __name__ == '__main__':
    s = Solution()
    board = [
        ['A', 'B', 'C', 'E'],
        ['S', 'F', 'C', 'S'],
        ['A', 'D', 'E', 'E']
    ]
    assert not s.exist(board, 'ABCB')
    assert s.exist(board, "ABCCED")
    assert s.exist(board, 'SEE')
